package com.google.codejam.qua2013.fairandsquare;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;

public class FairAndSquare {

    public static void main(String[] args) {
        String inputFile = args[0];
        String outputFile = args[1];
        readAndSolve(inputFile, outputFile);
    }

    public static String readAndSolve(String inFileName, String outFileName) {
        File file = new File(inFileName);
        BufferedReader bufferedReader = null;
        try {
            bufferedReader = new BufferedReader(new FileReader(file));
            FileWriter fileWriter = new FileWriter(outFileName, true);
            String readLine = null;
            int testCase = 0;
            int currentTestCaseIndex = 1;
            int line = 0;
            Long A = 0L;
            Long B = 0L;

            while ((readLine = bufferedReader.readLine()) != null) {
                if (readLine.trim().length() <= 0) {
                    continue;
                }
                if (line == 0) {
                    testCase = Integer.parseInt(readLine);
                    line++;
                    continue;
                }
                String[] interval = readLine.split(" ");
                A = Long.valueOf(interval[0]);
                B = Long.valueOf(interval[1]);
                int count = 0;
                for (Long i = A; i <= B; i++) {
                    Long sqrtValue = Double.valueOf(Math.sqrt(i)).longValue();
                    if (isPlalindrome(i) && isPlalindrome(sqrtValue) && sqrtValue * sqrtValue == i) {
                        count++;
                    }
                    Long next = (sqrtValue.toString().length() / 2) * 10 + sqrtValue;
                    next = next*next;
//                    System.out.println("next:"+next+", i:"+i);
                    i = next <= i ? ++i : next;
                }
                fileWriter.append("Case #" + currentTestCaseIndex + ": " + count);
                fileWriter.append("\n");
                // mark status
                if (currentTestCaseIndex == testCase) {
                    break;
                }
                currentTestCaseIndex++;
            }
            fileWriter.flush();
            fileWriter.close();
            bufferedReader.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
        return null;
    }

    public static boolean isPlalindrome(Long number) {
        String numStr = String.valueOf(number);
        return new StringBuffer(numStr).reverse().toString().equalsIgnoreCase(numStr);
    }
}
